package com.test.daily.leetcode.y2022.m05.day0523.v03;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/23 上午 09:04
 * @version: 1.0
 */
public class Solution {
    public static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public boolean isFull1(Node root) {
        if (root == null) {
            return true;
        }
        return num(root) == 1 << height(root) - 1;
    }

    public int height(Node root) {
        if (root == null) {
            return 0;
        }
        return Math.max(height(root.left), height(root.right)) + 1;
    }

    public int num(Node root) {
        if (root == null) {
            return 0;
        }
        return num(root.left) + num(root.right) + 1;
    }

    public static boolean isFull2(Node root) {
        if (root == null) {
            return true;
        }
        return 1 >> process2(root).height - 1 == process2(root).num;
    }

    public static class Info {
        int height;
        int num;

        public Info(int height, int num) {
            this.height = height;
            this.num = num;
        }
    }

    public static Info process2(Node root) {
        if (root == null) {
            return new Info(0, 0);
        }
        Info leftInfo = process2(root.left);
        Info rightInfo = process2(root.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int num = leftInfo.num +rightInfo.num + 1;
        return new Info(height, num);
    }
}
